package com.zzw.hj77;

import java.util.Scanner;
import java.util.*;

/**
 * @Project: hw_java
 * @Description: 火车进站
 * @Author: zzw
 */

public class Main2 {
    static List<String> res = new ArrayList<>();   //存放结果，也就是所有可能的出站序列

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            res.clear();
            int n = in.nextInt();//火车的数量
            int[] trains = new int[n];//存放火车编号
            Stack<Integer> station = new Stack<>();//用栈表示车站，只能先进后出
            for (int i = 0; i < n; i++) {
                trains[i] = in.nextInt();
            }
            trainOut(trains, 0, station, "", 0);
            Collections.sort(res);
            for (String s : res) {
                System.out.println(s);
            }
        }
        in.close();
    }

    /*
    DFS算法模板
    public static int dfs(int step){
        if(当前状态=目标状态){
            return ...;
        }
        for(查找新状态){
            标记状态;
            dfs(下一状态);
            撤销状态标记，也就是回溯;
        }
    }
    */
    public static void trainOut(int[] trains, int in, Stack<Integer> station, String resTemp, int out) {
        if (out == trains.length) {   //out表示已经出站的火车数量。当所有火车出站时，表示一个出站序列完成，将其添加到结果中
            res.add(resTemp);
        }
        if (!station.empty()) {  //当车站还有火车时
            int train = station.pop();  //出站一辆火车
            trainOut(trains, in, station, resTemp + train + " ", out + 1);//该出站火车添加到当前出站序列，出站火车数量+1
            station.push(train); //恢复现场，恢复进栈前的状态
        }
        if (in < trains.length) { //当还有火车未进站时
            station.push(trains[in]);//进站一辆火车
            trainOut(trains, in + 1, station, resTemp, out); //已进站火车数量+1
            station.pop(); //恢复出栈前的状态
        }
    }
}